package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


/**
 * @author: lynn
 * @Descript:  最近公共祖先
 * 给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先LCA
   https://developer.aliyun.com/article/780172
 * @date: 2021/6/6 21:54
 * @version: 1.0
 */
public class Q68_1_TreeNodeCommonParentNode {

   public static void main(String[] args) {
      TreeNode treeNode=new TreeNode(8);
      treeNode.left=new TreeNode(4);
      treeNode.right=new TreeNode(10);
      treeNode.left.left=new TreeNode(11);
      treeNode.left.right=new TreeNode(6);
      treeNode.right.left=new TreeNode(5);
      treeNode.right.right=new TreeNode(12);
      treeNode.right.right.right=new TreeNode(16);
      List<ArrayList<Integer>> list=findAllTreePath(treeNode);
      System.out.println(list);
   }
   private  static List<ArrayList<Integer>> findAllTreePath(TreeNode root){  //fixme 遍历获取所有的树的路径
      ArrayList<ArrayList<Integer>> res = new ArrayList();
      if(root == null) return res;
      Stack<Integer> stack = new Stack<Integer>();
      preOrder(root, stack,  res);
      return res;
   }

   public static void preOrder(TreeNode root, Stack<Integer> stack,List<ArrayList<Integer>> res){
      if(root == null){
         return;
      }
      stack.push(root.val);
      if(root.left == null && root.right == null){  //fixme 且的关系,总体思路是把stack放到res中
         ArrayList<Integer> one = new ArrayList();
         one.addAll(stack);//fixme 但是又不能直接放,用一个 add one
         res.add(one);
      }
      preOrder(root.left, stack, res);
      preOrder(root.right, stack,  res);
      stack.pop();//移除已经计算过的树节点
   }


   private static class TreeNode{
      TreeNode left;
      TreeNode right;
      int val;
      TreeNode(int val){
         this.val=val;
      }
   }
}
